/**
 * @Project : algorithm-learning
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/4/14 18:48
 */

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        int f[nums.size() + 1];
        f[0] = 0;
        int res = -0x3f3f3f3f;
        for (int i = 0; i < nums.size(); ++i) {
            f[i + 1] = max(f[i], 0) + nums[i];
            res = max(res, f[i + 1]);
        }
        return res;
    }
};

int main() {
    Solution sl;
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << sl.maxSubArray(nums);
    return 0;
}
